import copy


class Solution:
    # 用来判断9宫格的字典，实在想不出什么好方法了，用了一个最朴实的方法
    cent_dic = {0: 1, 1: 1, 2: 1, 3: 4, 4: 4, 5: 4, 6: 7, 7: 7, 8: 7}

    def solveSudoku(self, board):
        """
        Do not return anything, modify board in-place instead.
        """
        for hang_num, hang_list in enumerate(board):
            for lie_num, num in enumerate(hang_list):
                if num == ".":
                    board[hang_num][lie_num] = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]
        mid_board = copy.deepcopy(board)
        self.solution2(mid_board)
        for i in range(0, 9):
            for j in range(0, 9):
                board[i][j] = mid_board[i][j]

    def solution2(self, board):
        if self.solution(board):
            return True
        for hang_num, hang_list in enumerate(board):
            for lie_num, num in enumerate(hang_list):
                # if type(num) == list:
                if isinstance(num, list):
                    mid_num = num[:]
                    for i in mid_num:
                        mid_board = copy.deepcopy(board)
                        mid_board[hang_num][lie_num] = i
                        if self.solution2(mid_board):
                            continue
                        else:
                            for i in range(0, 9):
                                for j in range(0, 9):
                                    board[i][j] = mid_board[i][j]
                            return
                    else:
                        return True

    def solution(self, board):
        """这个函数可以把输入进来的数独尽可能地往下做，但是不会猜，如果后面有需要猜了做的无法完成

        :param board: 输入的数独数组
        :return: 由于后面猜的函数也调用了这个，猜一个数运行一次这个，所以如果猜错了，会导致某个格子的可能性归0，
        那么会return True，否则就会直接返回（None）
        """
        change_flag = False  # 由于有可能没做完的时候就无法进行了，所以需要一个变量判断是不是进行不下去了
        for hang_num, hang_list in enumerate(board):
            for lie_num, num in enumerate(hang_list):
                # 在某个格子还是一个列表的时候，就更新这个格子的可能性，需要注意排除自身
                if type(num) == list:
                    for i in range(0, 9):
                        if i != lie_num and (board[hang_num][i] in num):
                            num.remove(board[hang_num][i])
                            change_flag = True
                        if i != hang_num and (board[i][lie_num] in num):
                            num.remove(board[i][lie_num])
                            change_flag = True
                    # 下面这个直接取了这个元素9宫格内的元素，用最上面的字典
                    for j in range(self.cent_dic[lie_num] - 1, self.cent_dic[lie_num] + 2):
                        for i in range(self.cent_dic[hang_num] - 1, self.cent_dic[hang_num] + 2):
                            if j == lie_num and i == hang_num:
                                continue
                            # 如果某个格子是列表，那么下面这个判断一定是False，符合我们的预想
                            elif board[i][j] in num:
                                num.remove(board[i][j])
                                change_flag = True
                    # 如果只剩下一个可能性，那么就是它了
                    if len(num) == 1:
                        board[hang_num][lie_num] = num[0]
                    # 如果猜错了，就要返回True，让调用的函数去返回
                    elif len(num) == 0:
                        return True
        # 如果改不下去了，就返回
        if not change_flag:
            return
        # 如果改完还有某个格子是列表，就往下递归
        for hang_list in board:
            for num in hang_list:
                if type(num) == list:
                    return self.solution(board)


a = Solution()
b = [[".", ".", "9", "7", "4", "8", ".", ".", "."],
     ["7", ".", ".", ".", ".", ".", ".", ".", "."],
     [".", "2", ".", "1", ".", "9", ".", ".", "."],
     [".", ".", "7", ".", ".", ".", "2", "4", "."],
     [".", "6", "4", ".", "1", ".", "5", "9", "."],
     [".", "9", "8", ".", ".", ".", "3", ".", "."],
     [".", ".", ".", "8", ".", "3", ".", "2", "."],
     [".", ".", ".", ".", ".", ".", ".", ".", "6"],
     [".", ".", ".", "2", "7", "5", "9", ".", "."]]
# b= [["5", "3", ".", ".", "7", ".", ".", ".", "."],
#  ["6", ".", ".", "1", "9", "5", ".", ".", "."],
#  [".", "9", "8", ".", ".", ".", ".", "6", "."],
#  ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
#  ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
#  ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
#  [".", "6", ".", ".", ".", ".", "2", "8", "."],
#  [".", ".", ".", "4", "1", "9", ".", ".", "5"],
#  [".", ".", ".", ".", "8", ".", ".", "7", "9"]]
a.solveSudoku(b)
for i in b:
    for j in i:
        print(j, end="\t")
    print("")
